package chapter01;

public class SolveSudoku {
    /**
     * 回溯法
     * 思路：当前(x,y)不为'.',从1-9开始尝试将数字填充进(x,y)后判断填充后的行列以及九宫格是否合法
     *      若合法则继续填充(x,y+1)位置；若填充后不合法，则回撤(x,y)位置数字，从1-9中选择其他位置
     * 递归条件 dfs(x,y)
     *  1) x==9 说明0-8行没问题 返回true
     *  2) y==9 说明这一行已经尝试结束，接着尝试下一行
     *  3) 如果(x,y)不是数字，则跳过该位置，尝试(x,y+1)
     *  4) 否则从1-9中选择数字尝试填入(x,y)位置，如果填入后符合数独规则，判断之后的位置是否合法，若合法返回true;
     *     若1-9中选择的数字都不符合数独规则，返回false;
     */
    public void solveSudoku(char[][] board){
        dfs(board,0,0);
    }

    public boolean dfs(char[][] board,int x,int y){
        if(x==9){
            return true;
        }
        if(y==9){
            return dfs(board,x+1,0);
        }
        if(board[x][y]!='.'){
            return dfs(board,x,y+1);
        }
        for(int i=1;i<10;i++){
            char val=(char)('0'+i);
            if(vaild(board,x,y,val)){
                board[x][y]=val;
                if (dfs(board, x, y + 1)) {
                    return true;
                }
                board[x][y]='.';
            }
        }
        return false;
    }

    public boolean vaild(char[][] board,int row,int col,char val){
        for(int j=0;j<9;j++){
            if (board[row][j] >= '0' && board[row][j] <= '9') {
                if(board[row][j]==val){
                    return false;
                }
            }
        }
        for(int j=0;j<9;j++){
            if (board[j][col] >= '0' && board[j][col] <= '9') {
                if(board[j][col]==val){
                    return false;
                }
            }
        }
        row=row/3*3;
        col=col/3*3;
        for(int i=row;i<row+3;i++){
            for(int j=col;j<col+3;j++){
                if (board[i][j] >= '0' && board[i][j] <= '9') {
                    if(board[i][j]==val){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
